위상정렬(Topological Sort)

#Algorithm #Algorithm_Sort #Algorithm_Topological_Sort

1. Topological Sort?

위상(位相)이라는 말은 '위치 관계'라고 풀어 말할 수 있는데, 크게 감이 오는 설명은 찾을 수 없고 이를 토대로 위상 정렬을 개인적으로 이해해보고자 노력한 바로는, 위치(선, 후) 관계를 가진 노드들을 관계에 위배되지 않는 선에서 정렬한 것이라고 할 수 있다.

'위치 관계에 위배되지 않는'의 뜻은

1-1. 이어져야 한다?

그래프의 정렬이라고 하면 왠지 결과는 경로이어야 할 것 같다. 위상 정렬은 경로가 아니다. 위치 관계에 위배되지 않는 선에서의 '노드 순서' 이다. DFS가 아니라 BFS의 형태로 생각해야 한다.

1-2. 선행되는 위치 관계가 있다. 사이클이 생겼을 때는?

사이클이라는 것은 선행 위치 관계이자 후행 위치 관계를 동시에 만족할 수 있는 노드 관계가 존재한다는 것이다. 이것은 선행되는 위치 관계를 영원히 만족시킬 수 없다는 말이다. 위상 정렬을 하기 위해서는 사이클이 없는 그래프여야 한다.

1-3. 노드로의 진입 차수

방향성이 있는 그래프에서는 어떠한 노드'에서' 어떠한 노드'로' 이동하는 형태로 구성된다. A 노드에서 B 노드로 이동하게 된다면, B노드는 A노드로부터 진입된다고 할 수 있다. (=B 노드의 진입점 중 하나는 A 노드이다.) 이때 B 노드의 진입점의 갯수를 B 노드의 진입차수라고 한다.

1-4. 하나의 그래프, 여러개의 위상 정렬 결과

하나의 그래프에서 나올 수 있는 위상 정렬의 결과 값은 여러개이다.
위치 관계에 위배되지만 않는다면, 시작점을 어떤 노드로 지정하던지 상관이 없고, 다음 방문 노드도 상관이 없다.

1-5. 위상 정렬하는 방법 1-3. + 1-4.

정렬의 출발 노드는 어떻게 정할까? 선행되는 위치 관계가 없는 노드는 출발 대상 노드가 될 수 있지 않을까? 방향성을 거스를 선행노드가 없다는 뜻이기도 하니까?
그럼 그 다음 노드는 어떻게 정할까? 출발 노드가 유일한 진입점이였던 노드이면 또 위치 관계에 위배되지 않는 조건을 만족하지 않을까? 이렇게 귀납적으로 풀어가면 되지 않을까?

1-6. 마지막으로, 정렬 결과에 그래프의 노드 중 하나라도 빠진다면?

'정렬'은 주어진 모든 데이터에 대해서 이루어져야 한다. 하나라도 빠져있다면, 정렬되지 않았다는 것이다. 더 정확히 말해서 정렬될 수 없는 그래프라는 것이다. 위상정렬은 이 점을 유의해야 한다.

위상 정렬(Topological Sort)이란, heejeong Kwon
위의 포스트는 이미지로 설명이 잘 되어있다.

2. 구현

1-4의 방법처럼 진입 차수가 0인 노드들을 방문하면서, 이 노드를 선행 노드로 가지고 있는 노드들의 진입차수를 하나씩 낮추면서 0이 되는 노드를 다시 탐색하는 방식으로 구현한다. 이를 위해서는 queue와 진입차수의 변경을 저장할 배열을 이용한다.

2-1. 노드

data class TopologicalNode(  
    val key: Int,  
    val fromNode: ArrayList<TopologicalNode> = arrayListOf(), //이 노드가 도착지점이 되는 노드  
    val toNode: ArrayList<TopologicalNode> = arrayListOf() //이 노드에서 출발하여 도착지점이 되는 노드  
) {  
    fun addToNode(node: TopologicalNode) {  
        this.toNode.add(node)  
    }  
  
    fun addFromNode(node: TopologicalNode) {  
        this.fromNode.add(node)  
    }  
  
    companion object {  
        fun createGraph(): ArrayList<TopologicalNode> {  
            val node0 = TopologicalNode(0)  
            val node1 = TopologicalNode(1)  
            val node2 = TopologicalNode(2)  
            val node3 = TopologicalNode(3)  
            val node4 = TopologicalNode(4)  
            val node5 = TopologicalNode(5)  
  
            node0.addToNode(node2)  
            node0.addToNode(node3)  
  
            node1.addToNode(node3)  
            node1.addToNode(node4)  
  
            node2.addFromNode(node0)  
            node2.addToNode(node3)  
            node2.addToNode(node5)  
  
            node3.addFromNode(node0)  
            node3.addFromNode(node1)  
            node3.addFromNode(node2)  
            node3.addToNode(node5)  
  
            node4.addFromNode(node1)  
            node4.addToNode(node5)  
  
            node5.addFromNode(node2)  
            node5.addFromNode(node3)  
            node5.addFromNode(node4)  
  
            return arrayListOf(node0, node1, node2, node3, node4, node5)  
        }  
    }  
}

2-2. 정렬

class TopologicalSort {  
    fun sort(graph: ArrayList<TopologicalNode>) {  
        val zeroDegreeQueue: Queue<TopologicalNode> = LinkedList()  
        val degreeOfNode: IntArray = IntArray(graph.size)  
  
        for (node in graph) {  
            degreeOfNode[node.key] = node.fromNode.size  
            if (degreeOfNode[node.key] == 0) {  
                zeroDegreeQueue.offer(node)  
            }  
        }  
  
        while(zeroDegreeQueue.isNotEmpty()) {  
            val node = zeroDegreeQueue.poll()  
  
            print("${node.key}, ")  
  
            for(nextNode in node.toNode) {  
                degreeOfNode[nextNode.key] = degreeOfNode[nextNode.key]-1  
  
                if (degreeOfNode[nextNode.key] == 0) {  
                    zeroDegreeQueue.offer(nextNode)  
                }  
            }  
        }  
    }  
}

2-3. 테스트

fun main(args: Array<String>) {  
    val topologicalSort = TopologicalSort()  
	topologicalSort.sort(TopologicalNode.createGraph()) // 0, 1, 2, 4, 3, 5,   
}